This paper describes an optimization strategy of the highly active vinyl ketone 3 which was recognized as a strong inhibitor of rhodesain of Trypanosoma brucei rhodesiense, endowed with a ksecond value of 67 × 106 M-1 min-1 coupled with a high binding affinity (Ki = 38 pM). We now report a new structure-activity relationship study based on structural variations on the P3, P2, and P1' sites which led us to identify two potent lead compounds, i.e., vinyl ketones 4h and 4k. Vinyl ketone 4h showed an impressive potency toward rhodesain (ksecond = 8811 × 105) coupled to a good antiparasitic activity (EC50 = 3.6 μM), while vinyl ketone 4k proved to possess the highest binding affinity toward the trypanosomal protease (Ki = 0.6 pM) and a submicromolar antiparasitic activity (EC50 = 0.67 μM), thus representing new lead compounds in the drug discovery process for the treatment of Human African Trypanosomiasis.